package algorithm.middle;

import java.util.*;

public class Insert57 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{newInterval};
        }
        int start = newInterval[0];
        int end = newInterval[1];
        List<int[]> list = new ArrayList<>();
        //1-左端点处理，2-右端点处理，3-处理完
        int flag = 1;
        int[] temp = new int[]{start,end};
        for (int[] arr : intervals) {
            if (flag==1){
                if (end < arr[0]) {
                    list.add(temp);
                    list.add(arr);
                    flag = 3;
                } else if (end<=arr[1]) {
                    arr[0] = Math.min(start, arr[0]);
                    list.add(arr);
                    flag = 3;
                } else if (start <= arr[1]) {
                    temp[0] = Math.min(start, arr[0]);
                    list.add(temp);
                    flag = 2;
                }else {
                    list.add(arr);
                }
            }else if (flag==2){
                if (end < arr[0]) {
                    list.add(arr);
                    flag = 3;
                } else if (end < arr[1]) {
                    list.get(list.size() - 1)[1] = arr[1];
                    flag = 3;
                }else {
                    //ignore
                    continue;
                }
            }else {
                list.add(arr);
            }

        }
        if (flag == 1) {
            list.add(temp);
        }
        int[][] array = list.toArray(new int[list.size()][]);
        return array;
    }


    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
            map.computeIfAbsent(getKey(str), k->new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    private String getKey(String str) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        String res = "";
        for (char c : charArray) {
            res += c;
        }
        return res;
    }
}
